#include <stdio.h>
#include <stdlib.h>
typedef int ElementType; // 元素类型 (typedef作用是起别名)
#define MAX_SIZE 100

//栈
typedef struct {
    ElementType *data; // 数据数组
    int top; // 栈顶指针
} Stack;

//初始化栈
Stack* InitStack() {
    Stack* s = (Stack*)malloc(sizeof(Stack)); // 动态分配内存
    s->data = (ElementType*)malloc(sizeof(ElementType) * MAX_SIZE);
    s->top = -1; // 栈为空
    return s;
}


//判断栈是否为空
int IsEmpty(Stack* s) {
    if (s -> top  == -1) {
        printf("栈空\n");
        return 1; // 栈空
    }
    else {
        printf("栈不空\n");
        return 0; // 栈不空
    }
}
//获取栈顶元素
int Peek(Stack* s, ElementType* value) {
    if (IsEmpty(s)) return 0; // 栈空
    *value = s->data[s->top]; // 获取栈顶元素
    return 1;
}
//入栈
int Push(Stack* s, ElementType value) {
    if (s->top == MAX_SIZE - 1) return 0; // 栈满
    // s->data[++s->top] = value; // 入栈(等价于下面两行)

    // ++a 是前置自增，即先加再用
    // a++ 是后置自增，即先用再加
    // 因为top是从-1开始的，所以要先加1再赋值

    s->top++; // 栈顶指针加1
    s->data[s->top] = value; // 入栈
    return 1;
}

//出栈
int Pop(Stack* s, ElementType* value) {
    if (IsEmpty(s)) return 0; // 栈空
    // *value = s->data[s->top--]; // 出栈（等价下面两行）

    *value = s->data[s->top]; // 先获取栈顶元素
    s->top--; // 栈顶指针减1

    // 出栈不是真的删除元素，而是让栈顶指针减1
    // top指向的元素就不在栈中
    // 这和顺序表中让length减1是一样的，并不是真的删除元素
    // 等到下一次入栈时，新的元素会覆盖原来的元素。
    return 1;
}



//清空栈
int clearStack(Stack* s) {
    s->top = -1; // 让栈顶指针指向-1
    return 1;
}

int main(){
    Stack* s = InitStack(); // 初始化栈
    Push(s, 1);
    Push(s, 2);
    Push(s, 3);
    Push(s, 4);

    ElementType value; // 定义变量存储出栈元素(根据上面的函数，value存储着栈顶元素)
    Pop(s, &value);
    printf("出栈元素: %d\n", value);
    Peek(s, &value);
    printf("栈顶元素: %d\n", value);
    clearStack(s);
    free(s->data);
    free(s);
    return 0;
}